/*
 *
 */


/******************************************************************************/

/*
 * 树的双亲表示法:
 * 以一组连续空间存储树的特点，同时在每个结点中，附设一个指示器指示其双亲结点
 * 在数组中的位置。
 */
#define MAX_TREE_NUM 100

typedef int ElemType;   /* 树结点的数据类型 */

/* 结点结构 */
struct node {
    ElemType data;  /* 结点数据 */
    int parent;     /* 双亲位置 */
};

/* 树结构 */
struct tree {
    struct node nodes[MAX_TREE_NUM];  /* 结点数组 */
    int root, num;                    /* 根的位置和结点数 */
};
typedef struct tree tree_t;


/******************************************************************************/

/* 不确定是不是这样写 */

/*
 * 多重链表表示法
 * 每个结点有多个指针域，其中每个指针指向同一颗子树的根结点。
 * 方案一: 指针域的个数等于树的度
 * 方案二: 每个结点指针域的个数等于该结点的度，用一个位置来存储结点指针域的个数
 */

/* 结点结构
 * 方案一: 假设树的度为3(即树内各结点的度的最大值)
 */
struct node {
    ElemType data;  /* 结点数据 */
    struct node *child1;     /* 指向孩子1结点 */
    struct node *child2;     /* 指向孩子2结点 */
    struct node *child3;     /* 指向孩子3结点 */
};

/*
 * 方案二
 * 这个是伪代码，类似这样写了。指向孩子结点的指针数组，根据结点个数申请内存
 * 没想到具体是怎么写
 */
struct node {
    ElemType data;  /* 结点数据 */
    int degree;     /* 孩子结点个数 */
    struct node *child;     /* 指针数组，指向孩子结点 */
};

typedef struct node tree_t;
tree_t *root; /* 头指针，指向根结点 */



/******************************************************************************/


/*
 * 孩子表示法
 * 把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，
 * 如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储
 * 结构，存放在一个一维数组中。
 */

#define MAX_TREE_NUM 100

typedef int ElemType;   /* 树结点的数据类型 */

/* 孩子结点 */
struct child_node  {
    int child;                /* 存储结点在表头数组的下标 */
    struct child_node *next;  /* 指向下一个孩子结点的指针 */
};

/* 表头结构 */
struct tree_header {
    ElemType data;                   /* 结点数据 */
    struct child_node *first_child;  /* 孩子链表的头指针 */
};

struct tree {
    struct tree_header[MAX_TREE_NUM];   /* 结点数组 */
    int root, node_nums;                /* 根位置 和 结点数 */
};

struct tree  tree_t;


/******************************************************************************/


/*
 * 孩子兄弟表示法
 * 任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是
 * 唯一的。因此可以设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
 */

struct node {
    ElemType data;
    struct node  *first_child, *right_sib;
};






